def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr


def insert_sort(arr):
    for i in range(1, len(arr)):
        cur = arr[i]
        pre = i-1
        while pre >= 0 and arr[pre] > cur:
            arr[pre+1] = arr[pre]
            pre -= 1
        arr[pre+1] = cur
    return arr


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    p = arr[0]
    less = [i for i in arr[1:] if i <= p]
    more = [i for i in arr[1:] if i > p]
    return quick_sort(less) + [p] + quick_sort(more)


if __name__ == "__main__":
    arr = [45, 3, 55, 23, 3434, 34, 4, 1]
    # print("bubble_sort:", bubble_sort(arr))
    print("insert_sort:", insert_sort(arr))
    # print("quick_sort:", quick_sort(arr))
    # print("binary_search:", binary_search(quick_sort(arr), 3434))
